
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    /**
     * 第一遍
     * @param headA
     * @param headB
     * @return
     */
//    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//        ListNode p1 = headA, p2 = headB;
//        while (p1 != p2) {
//            // p1遍历完之和遍历p2
//            if (p1 == null) p1 = headB;
//            else p1 = p1.next;
//            if (p2 == null) p2 = headA;
//            else p2 = p2.next;
//        }
//        return p1;
//    }

    /**
     * 第二遍
     * @param headA
     * @param headB
     * @return
     */
//    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//        ListNode p1 = headA, p2 = headB;
//        while (p1 != p2) {
//            if (p1 == null) p1 = headB;
//            else p1 = p1.next;
//            if (p2 == null) p2 = headA;
//            else p2 = p2.next;
//        }
//        return p1;
//    }


    /**
     * 第三遍
     * @param headA
     * @param headB
     * @return
     */
//    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//        ListNode p1 = headA;
//        ListNode p2 = headB;
//
//        while (p1 != p2) {
//            if (p1 == null) p1 = headB;
//            else p1 = p1.next;
//            if (p2 == null) p2 = headA;
//            else p2 = p2.next;
//        }
//        return p1;
//    }



    /**
     * 第四遍 2/27
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA;
        ListNode p2 = headB;

        while (p1 != p2) {
            if (p1 != null) p1 = p1.next;
            else p1 = headB;
            if (p2 != null) p2 = p2.next;
            else p2 = headA;
        }
        return p1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
